package leetcode_滑动窗口;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 毯子覆盖的最多白色砖块数
 * <p>
 * 实际上，毯子右端点放在一段瓷砖中间，是不如直接放在这段瓷砖右端点的（因为从中间向右移动，能覆盖的瓷砖数不会减少），所以可以枚举每段瓷砖的右端点来摆放毯子的右端点。
 *
 * @author yezh
 * @date 2025/1/6 17:19
 */
public class _2271 {

    public int maximumWhiteTiles(int[][] tiles, int carpetLen) {
        Arrays.sort(tiles, Comparator.comparingInt(o -> o[0]));
        int ans = 0, n = tiles.length, left = 0, cover = 0;
        for (int i = 0; i < n; i++) {
            int curL = tiles[i][0], curR = tiles[i][1];
            // 1.右边进 - 固定窗口右边, 覆盖的范围 [curR - carpetLen + 1, curR]
            cover += curR - curL + 1;
            // 2.左边出 - 找到窗口左边
            while (curR - carpetLen + 1 > tiles[left][1]) {
                cover -= tiles[left][1] - tiles[left][0] + 1;
                ++left;
            }
            // 如果毯子左端点在瓷砖段 tiles[left] 内部，则覆盖的瓷砖数还需要额外减去这段瓷砖没被覆盖的部分
            int uncover = Math.max(curR - carpetLen - tiles[left][0] + 1, 0);
            ans = Math.max(ans, cover - uncover);
        }
        return ans;
    }

}
